A distributed computer system includes several processors that cooperate to perform a task. To cooperate more effectively, the processors often send messages to each other. One method of sending a message from one processor to another is to write the message in a shared memory and to arrange for each processor to periodically scan the shared memory for messages.
When a scanning processor scans the shared memory for messages, it typically locks the shared memory so that no other processor can access it. The scanning processor then scans the destination addresses for the messages in the shared memory and reads those that are addressed to it. Once the scanning processor has scanned the shared memory, it unlocks it so that other processors can again gain access to it.
As the number of processors sharing the memory becomes larger, the number of processors that periodically scan the memory inevitably increases. As the number of processors increases, the number of messages in shared memory usually increases. As a result, each such scan takes longer. With more processors scanning progressively more messages, and with only one processor at a time scanning the shared memory, it is no surprise that the fraction of the time during which shared memory is locked by a scanning processor increases. As a result, the probability that the shared memory will be locked when a processor requires access to it increases.
In a conventional messaging system, the scanning processor can take up to 1000 microseconds to complete a scan. Since a typical processor will scan for messages up to sixty times per second, each processor locks shared memory for up to 60,000 microseconds every second. With only ten processors, shared memory can be locked for as long as 600,000 microseconds every second. This is already more than half of the 1,000,000 microseconds available in every second. It is foreseeable, therefore, that as the number of processors increases, messages of great urgency may not be posted in shared memory promptly.
As messages accumulate in shared memory, it becomes necessary to remove those that have been read by their intended recipients. This task, which is referred to as “garbage collection”, is typically performed by a separate utility that deletes messages that have already been read. During this process, shared memory is again locked. This further increases the fraction of time during which shared memory is unavailable to other processors.